`
https://leetcode.cn/problems/find-substring-with-given-hash-value/
`

/**
 * @param {string} s
 * @param {number} power
 * @param {number} modulo
 * @param {number} k
 * @param {number} hashValue
 * @return {string}
 */
var subStrHash = function (s, power, modulo, k, hashValue) {
  power = BigInt(power)
  modulo = BigInt(modulo)
  hashValue = BigInt(hashValue)
  const n = s.length
  const val = (s, i) => BigInt(s.charCodeAt(i) & 31)

  // 计算 s[n-k:] 的哈希值，同时计算 pk
  let hash = 0n, pk = 1n
  for (let i = n - 1; i >= n - k; i--) {
    hash = (hash * power + val(s, i)) % modulo
    pk = (pk * power) % modulo
  }

  let res = hash === hashValue ? n - k : 0

  // 倒着遍历，向左滑窗
  for (let i = n - k - 1; i >= 0; i--) {
    // 计算新的哈希值，注意 + modulo 防止计算出负数
    hash = (hash * power + val(s, i) - pk * val(s, i + k) % modulo + modulo) % modulo;
    if (hash === hashValue) {
      res = i;
    }
  }

  return s.substring(res, res + k)
};